Packet data systems are typically used for communications networks and a variety of protocols have developed to regulate transmission and receipt of data packets on such networks. As long as the ideal error-free communication channel has not been realized, data communication on such networks generally allows, among other things, for retransmission of data when errors are detected. Various protocols governing data transmission have evolved in an attempt to allow reliable data communications and to maximize network utilization. The need for optimizing channel utilization becomes even more pronounced where a heavily utilized wireless communication network such as a cellular or PCS system or a wire line network comprises a portion of the data communications network.
Typical packet data systems include a forward channel, generally referred to as a downlink (from base to portable) in a wireless network, and a reverse channel, typically referred to as an uplink (from portable to base) in a wireless network. The forward (or downlink) channel is typically a constant stream of data messages which are broadcast from a base station to a population of listening subscriber devices. The forward channel is a one to many broadcast channel. The reverse channel (or uplink) is shared by the population of subscriber devices and, as a consequence, is often referred to as a many-to-one channel. This immediately highlights that the access to the reverse channel by the subscribers must be carefully managed due to the risk of multiple devices attempting to use the channel at the same instant, which results in collisions and a waste of the available bandwidth. The difficulty of channel management is exacerbated because a "listen before transmission" policy is generally hampered because the subscriber population is geographically distributed. As a consequence, subscribers may not ascertain if the reverse channel is currently being utilized by another subscriber. This is known as the hidden terminal problem.
Packet data multiple access protocols are generally classified into two categories: contention protocols (such as Aloha and CSMA) or packet reservation protocols (such as PRMA). When employed in a digital packet radio system, these systems generally employ control flags that are broadcast on the forward channel to inform the population of subscriber devices the status of the reverse channel. This approach eliminates the hidden terminal problem since all subscribers receive the forward channel. Contention schemes usually utilize a small window in which access is permitted. If a single transmission occurs, the control flags inform the remaining members of the subscriber population not to transmit, allowing the channel to become dedicated to the transmitting subscriber. However, if two transmissions occur at the same instant a collision occurs and channel bandwidth is wasted.
Packet reservation schemes manage the available channel bandwidth by either polling each subscriber in turn and dedicating the reverse channel if the subscriber has messages to transmit, or by providing a predefined periodic short contention window portion of each block in which very short reservation requests may be transmitted. Upon receipt of a successful reservation request, the channel will be allocated to the specific subscriber. The reservation transmission is regarded as very efficient since wastage due to subscriber transmission collisions generally does not occur.
In general, both categories of multiple access protocols have significant system advantages and disadvantages. The typical construction of an Aloha Contention Protocol is illustrated in FIG. 1. As illustrated in FIG. 1, synchronization words are imbedded in the forward channel at regular intervals which, in turn, delineate the reverse channel into dedicated transmission slots. A subscriber device is permitted to transmit a data packet in any slot. As a consequence, the utilization of a slot may be classified as a success, idle, or collision. A collision is defined when energy is present within slot boundaries but fails to decode which indicates that one or more transmissions from different devices probably occurred. Idle slots are devoid of energy from subscriber transmissions and successful receipt of a transmission burst from a subscriber indicates successful utilization of a slot. Collision and idle slots represent a waste of available reverse channel bandwidth.
Aloha type contention schemes generally provide for inefficient reverse channel utilization where long data packet transmissions such as file transfers are regularly encountered on the network. Such systems are also prone to instability with increasing access rates resulting in increased collisions followed by an increase in retransmission attempts which effectively continues to increase the demand on the network. Back-off policies are typically provided to reduce the risk of system instability. Aloha systems do, however, allow the use of slow receive to transmit switching time devices thereby allowing the use of low cost, half-duplex hardware.
A second type of contention scheme is a carrier sense multiple access (CSMA) protocol, the operations of which are illustrated in FIG. 2. Embedded in the forward channel is a sequence of control flags. Each control flag delineates the reverse channel into a sequence of collision windows and in addition indicates whether the reverse channel is currently being utilized (busy/idle) by a subscriber device. A subscriber device which has an outstanding data packet(s) for transmission determines if the channel is busy or idle prior to transmission. Furthermore, if the channel is sensed to be idle, the transmission occurs such that the reverse channel synchronization word is received by the base station prior to the transmission of the next busy/idle flag. This requirement ensures that the base station is able to set the busy/idle flag to busy, thereby protecting the remaining segments of the reverse channel subscriber transmission from interference from other subscriber devices that may have outstanding data packets ready for transmission. The technique allows the subscriber device to transmit variable length messages on the reverse channel without contending for the channel for each packet that requires transmission. Collisions may, however, occur during the collision window when the channel may be sensed to be idle by multiple subscribers with outstanding packets.
A further variant on the CSMA protocol is available if full duplex is employed. A subscriber device communicating on the reverse channel can then monitor the forward channel during the transmission of a set of data packets. The forward channel control device such as the base station can then alert a subscriber device if a collision has occurred and preempt termination of the transmission thereby conserving reverse channel bandwidth that may then be exploited by a different subscriber device. This approach is typically referred to as CSMA/CD (collision detect).
A disadvantage of the CSMA scheme is the need for fast receive to transmit switching times which typically means this protocol is inappropriate for use with inexpensive devices which may be desirable, particularly in a wireless environment. As CSMA is fundamentally a contention scheme, a back-off policy is typically provided as with Aloha due to the risk of system instability. An additional disadvantage of CSMA schemes is that they typically provide relatively poor channel utilization for a very short transmission packet environments.
An example of a packet reservation type multiple access is illustrated in FIG. 3. The Packet Reservation Multiple Access (PRMS) schemes are typically characterized by the partitioning of the reverse channel into a polling region and a reservation/data region. The polling region includes short slots, with each slot dedicated to a specific subscriber or device. A device utilizes this slot to announce to the system that it has outstanding data packets and that it requires a data slot to be reserved. If the forward channel device determines that a specific data slot within the reservation region is not utilized then it may allocate the particular data slot to a requesting reverse channel device for transmission of the outstanding frames. Ordinarily, a single data slot is commensurate with the largest possible packet or transmission block. A reverse channel device may identify that the reverse channel has been exclusively reserved for it by identifying that the reservation identifier flag embedded in the forward channel has been set to its identification value. However, this approach wastes channel bandwidth for very small messages, such as system acknowledgements and polling slots that are left empty for each reverse channel device that is polled but does respond because it does not have data packets to transmit. Such schemes do, however, typically allow for the use of low cost slower receive to transmit switching speed technology.
Contention based protocols are subject to instability because collisions may occur which in turn require increased attempts due to retransmission attempts. As traffic increases, utilization of the multiple access reverse channel typically drops due to increased numbers of collisions. The collision messages then are submitted for retransmission which causes the actual attempt rate (as opposed to the new arrival rate) to steadily increase without bound and once the optimal attempt rate has been passed the system utilization steadily falls. Eventually, all transmission slots may become filled with collisions and the system utilization will reach zero. This results in both a loss of revenue bearing traffic for the channel and typically dramatically increases the delay associated with delivery of data packets. This scenario is generally referred to as Aloha or reverse channel collapse.
To prevent Aloha instability, it is known to implement back-off procedures in contention based protocols. A subscriber device is only permitted to re-transmit each packet a finite number of times. Furthermore, each re-transmission is required to be delayed by an exponentially increased delay. This back-off policy does not eliminate the possibility that system instability can occur but the possibility is significantly reduced. Furthermore, if the channel utilization does fall because the attempt rate has exceeded the maximum that the system can support, then the back-off policy provides a mechanism for recovery if instability occurs.
Back-off rules typically involve two components. First, if a transmission attempt fails then the subscriber device will delay a subsequent transmission attempt by a random time interval. Second, if the number of transmission attempts exceeds a predetermined threshold then the subscriber device will discard the queued packet and abort the transmission attempt. The first rule minimizes the possibility that two or more subscriber devices will execute re-transmission attempts after an initial collision in an identical time slot. This approach provides an effective splitting algorithm that prevents continuous repeating collisions but it does not reduce the actual attempted traffic. The second rule provides a form of non-persistence which allows the system to recover. The rule effectively increases the departure rate, and departures are now partitioned between those that are successfully transmitted and those that are abandoned.
The above stabilization procedure is generally only viable in systems where the contribution to the attempted traffic from new arrivals is essentially steady, predictable and sufficiently low so that the total attempted traffic rate can remain at or below unity. The technique can control short term transient increases in the arrival rate, which are assumed to be infrequent, and the associated loss in channel utilization can be tolerated. However, if the number of new arrivals exceeds the departure rate (both successful and aborted) then the system may continue to drift to lower utilization. However, even though such a channel is incapable of supporting the entire traffic volume, utilization may fall to where the channel is unable to provide optimal utilization for even a portion of the traffic volume because of the limitations of these previously known stabilization techniques. This problem is a particular concern for radio or wireless packet data systems such as commercial, two-way, paging and message systems which include a mix of short and extended message traffic. To summarize, reverse channel Aloha collapse is undesirable because the revenue stream generated by the cell is significantly reduced, subscriber devices burn excess battery power through multiple fruitless transmission attempts and message center originated messages will suffer an inordinate acknowledgment time while subscribers will be prevented from initiating and successfully transmitting a data packet.